package cn.edu.jxau.test;

import java.util.NoSuchElementException;

/**
 * 大顶堆实现的优先队列
 * 
 * @author 付大石
 */
public class MaxPQ {

    /**
     * 小顶堆
     */
    private int[] pq;

    /**
     * 元素个数
     */
    private int size;

    public MaxPQ(int capacity) {

        pq = new int[capacity + 1];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void insert(int i) {
        pq[++size] = i;
        swim(size);
    }

    public int delMax() {

        if (isEmpty()) {
            throw new NoSuchElementException("优先队列为空");
        }
        int min = pq[1]; // 大顶堆的堆顶为最大值
        swap(1, size--);
        sink(1);
        return min;
    }

    private void swap(int i, int j) {

        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    private void sink(int k) {

        int target = pq[k];
        while (2 * k <= size) {
            int i = 2 * k;
            if (i + 1 <= size && pq[i] < pq[i + 1]) { // 找到左右孩子中较大的一个
                i++;
            }
            if (target > pq[i]) {
                break;
            }
            pq[k] = pq[i];
            k = i;
        }
        pq[k] = target;
    }

    public int max() {
        return pq[1];
    }

    private void swim(int k) {

        int target = pq[k];
        while (k > 1 && target > pq[k / 2]) {
            pq[k] = pq[k / 2];
            k = k / 2;
        }
        pq[k] = target;
    }
}
